Search for: All records

Inspired by the study of generic and coarse computability in computability theory, we extend such investigation to the context of computable model theory. In this paper, we continue our study initiated in the previous paper (Journal of Logic and Computation 32 (2022) 581–607) , where we introduced and studied the notions of generically and coarsely computable structures and their generalizations. In this paper, we introduce the notions of generically and coarsely computable isomorphisms, and their weaker variants. We sometimes also require that the isomorphisms preserve the density structure. For example, for any coarsely computable structure A, there is a density preserving coarsely computable isomorphism from A to a computable structure. We demonstrate that each notion of generically and coarsely computable isomorphisms, density preserving or not, gives interesting insights into the structures we consider, focusing on various equivalence structures and injection structures. 

In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x 0 < a 0 is ⩽ a 1 and such that every enumeration degree x 1 < a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that every enumeration degree x < a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair.